package com.noahsloan.groovy.algorithms

import com.noahsloan.groovy.util.Infinity

/**
 * @author noah
 *
 */
public class GraphAlgorithms {

	private static def fill(obj,Map... props) {
		props*.each { k, v -> obj[k] = v }
		obj
	}
	
	static def createNode = { data, Map properties = [:] ->
		fill( new Node(), [ createEdge:createEdge, data:data,
            incoming:new LinkedHashSet(), outgoing:new LinkedHashSet() ], 
            properties)
	}
	
	static def createEdge = { start, end, Map properties = [:] ->
		fill( new Edge(),[start:start,end:end], properties )
	}
	
	private def relax = { edge, dist, pred ->
		def start = edge.start, end = edge.end,
			total = dist[start]?.plus( getCost(edge) )
		if( Infinity.compare(total,dist[end]) < 0 ) {
			dist[end] = total
			pred[end] = start
			return true
		}
		return false
	}

	private def getCost(edge) {
		edge.cost == null ? 1 : edge.cost
	}
	
	/**
	 * Faster, but only works if edge weights are positive
	 */
	def fastShortestPaths(graph,startNode = graph.nodes.values().find{it}){
		// Dijkstra's Algorithm
		def dist = [:], pred = [:] 
		def remaining = new PriorityQueue(graph.size(), { a,b ->
			Infinity.compare(dist[a],dist[b])
		} as Comparator )
		dist[startNode] = 0
		graph.nodes.values().each remaining.&offer // log N
		
		// N + E(edge relaxations in loop)
		while(!remaining.isEmpty()) {
			// lg N (poll)
			remaining.poll().outgoing.each{ 
				if(relax(it,dist,pred)) {
					// if the distance changed, position changes
					// TODO should be increment key (lg N) need custom heap
					remaining.remove(it.end) // N
					remaining.offer(it.end) // lg N
				}
			}
		}
		
		[distance: dist, predecessor: pred]		
	}
	/**
	 * 
	 * Assumes edge cost of 1 if edge.cost returns null
	 * @return Map:
	 *  * distance = Map<Node,distance from start>
	 *  * predecessor = Map<Node,previous Node in shortest path tree>
	 *  * success = true if there are no negative weight circular paths.
	 *    These are bad because you can follow them to accumulate negative 
	 *    distance forever, meaning there is no shortest path.
	 */
	def shortestPaths(graph,startNode = graph.nodes.values().find{it}) {
		 // Bellman-Ford Algorithm
		def dist = [:], pred = [:], edges = graph.nodes.values()*.outgoing.flatten()
		
		dist[startNode] = 0

		// N
		1.upto(graph.nodes.size()-1) {
			// E
			edges.each { relax(it,dist,pred) }
		}
		// E
		def success = edges.every { edge ->
			Infinity.compare(
					dist[edge.end],
					dist[edge.start]?.plus( getCost(edge) ))  <= 0
		}
		[distance: dist, predecessor: pred, success:success]		
	}
	
	static final int UNVISTED = 0
	static final int VISITING = 1
	static final int VISITED  = 2
	
	/**
	 * 
	 */
	def depthFirstSearch(graph, pre = {}, post = {}) {
		def color = [:], pred = [:], time = 0, 
			fin = [:], disc = [:], edgeState = [:]
		
		def visit = { node ->
			pre(node)
			disc[node] = ++time
			color[node] = VISITING
			node.outgoing.each { edge ->
				def end = edge.end
				edgeState[edge] = color[end]
				if(color[end] == UNVISTED) {
					pred[end] = node
					visit(end)
				}
			}
			color[node] = VISITED
			fin[node] = ++ time
			post(node)
		}
		
		graph.nodes.values().each { 
			if(color[it] == UNVISTED) {
				visit(it)
			}
		}
		
		[edgeState:edgeState,predecessor: pred,finish:fin,discovery: disc]
	}
	
	def topologicalSort(graph) {
		def sorted = []
		depthFirstSearch(graph,null) { sorted << it }
		sorted
	}
	
	/**
	 * 
	 */
	def breadthFirstSearch(graph,startNode = graph.nodes.values().find{it}) {
		def queue = new LinkedList(),
			dist = [:], color = [:], pred = [:]
		graph.nodes.values().each { n ->
			color[n] = UNVISTED
		}
		color[startNode] = VISITING
		dist[startNode] = 0

		queue << startNode
		while(!queue.isEmpty()) {
			def cur = queue.removeFirst()
			cur.outgoing.each { edge ->
				def n = edge.end
				if( color[n] == UNVISTED ) {
					color[n] = VISITING
					dist[n] = dist[cur] + 1
					pred[n] = cur
					queue << n
				}
			}
			color[cur] = VISITED
		}
		[distance: dist, predecessor: pred]
	}
}
